package leetcode.graph;

import java.util.*;

public class CourseScheduleII210 {
    class Solution1 {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            if (numCourses <= 0) {
                return new int[0];
            }

            HashSet<Integer>[] adj = new HashSet[numCourses];
            for (int i = 0; i < numCourses; i++) {
                adj[i] = new HashSet<>();
            }

            // [1,0] 0 -> 1
            int[] inDegree = new int[numCourses];
            for (int[] p : prerequisites) {
                adj[p[1]].add(p[0]);
                inDegree[p[0]]++;
            }

            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < numCourses; i++) {
                if (inDegree[i] == 0) {
                    queue.add(i);
                }
            }

            int[] res = new int[numCourses];
            // 当前结果集列表里的元素个数，正好可以作为下标
            int count = 0;

            while (!queue.isEmpty()) {
                // 当前入度为 0 的结点
                Integer head = queue.poll();
                res[count] = head;
                count++;

                Set<Integer> successors = adj[head];
                for (Integer nextCourse : successors) {
                    inDegree[nextCourse]--;
                    // 马上检测该结点的入度是否为 0，如果为 0，马上加入队列
                    if (inDegree[nextCourse] == 0) {
                        queue.add(nextCourse);
                    }
                }
            }

            // 如果结果集中的数量不等于结点的数量，就不能完成课程任务，这一点是拓扑排序的结论
            if (count == numCourses) {
                return res;
            }
            return new int[0];
        }
    }

    class Solution2 {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
           if (numCourses <= 0) {
               return new int[]{};
           }
           Set<Integer>[] adj = new HashSet[numCourses];
            for (int i = 0; i < numCourses; i++) {
                adj[i] = new HashSet<>();
            }
            int[] inDegrre = new int[numCourses];
            for (int[] p : prerequisites) {
                adj[p[1]].add(p[0]);
                ++inDegrre[p[0]];
            }
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < numCourses; i++) {
                if (inDegrre[i] == 0) {
                    queue.add(i);
                }
            }
            int[] ans = new int[numCourses];
            int count = 0;
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                ans[count++] = cur;
                for (int next : adj[cur]) {
                    if (--inDegrre[next] == 0) {
                        queue.add(next);
                    }
                }
            }
            if (numCourses == count) {
                return ans;
            }
            return new int[]{};
        }
    }
}
